/*
 * @Author: szx
 * @Date: 2022-06-02 16:04:11
 * @LastEditTime: 2022-06-02 16:30:45
 * @Description:
 * @FilePath: \leetcode\400-499\473\473.js
 */
/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
let makesquare = (nums) => {
    if (nums.length < 4) return false;
    let total = nums.reduce((index, x) => (x += index));
    if (total % 4) return false;
    // 排序，从大到小
    nums.sort((a, b) => b - a);
    // 这样子写也行，因为上面已经确定是4的倍数了
    const SIDE = total / 4;
    if (nums[0] > SIDE) return false;
    let edges = [0, 0, 0, 0];

    // 回溯加上剪枝
    const dfs = (index) => {
        if (index === nums.length) return true;
        for (let i = 0; i < 4; i++) {
            // 因为排过序了，所以放不进去就直接pass就行了
            // 但这里还有个取巧的东西，如果i大于0，并且和前面一条相等，那么也跳过，说是为了保持一致性，这个我真没想到
            if (edges[i] + nums[index] > SIDE || (i && edges[i] === edges[i - 1])) continue;
            edges[i] += nums[index];
            if (dfs(index + 1)) return true;
            edges[i] -= nums[index];
        }
        return false;
    };
    return dfs(0);
};